# 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
#  你可以假设数组是非空的，并且给定的数组总是存在多数元素。
#
#  示例 1：
# 输入：[3,2,3]
# 输出：3
#
#  示例 2：
# 输入：[2,2,1,1,1,2,2]
# 输出：2
from typing import List


class Solution:
    def majorityElement4(self, nums: List[int]) -> int:
        """
        Boyer-Moore 投票算法(分治的变形)
        :param nums:
        :return:
        """
        count = 0  # 候选众数出现的次数
        candidate = None  # 候选众数

        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)  # 当前数和候选数相等计数器+1，不等计数器-1

        return candidate

    def majorityElement3(self, nums: List[int]) -> int:
        """
        解法三:分治(时间复杂度 nlogn)
        该问题其实就是众数问题
        如果数 a 是数组 nums 的众数，如果我们将 nums 分成两部分，那么 a 必定是至少一部分的众数。
        具体做法:
            将数组分成左右两部分，分别求出左半部分的众数 leftMode 以及右半部分的众数 rightMode，
            随后在 leftMode 和 rightMode 中选出正确的众数。
        :param nums:
        :return:
        """
        def majorityElementRange(low, high) -> int:
            if low == high:
                return nums[low]
            mid = (high - low) // 2 + low
            # 递归求两部分的众数
            leftMode = majorityElementRange(low, mid)
            rightMode = majorityElementRange(mid + 1, high)
            if leftMode == rightMode:  # 左右两部分众数相同，说明找到了数组在[low,high]区间的众数，返回即可
                return leftMode
            # 否则需要分别统计nums数组[low, high]等于leftMode和rightMode的个数，且这两个数出现次数谁多谁是整个区间[low,high]的众数
            leftModeCount = sum([1 for i in range(low, high + 1) if nums[i] == leftMode])
            rightModeCount = sum([1 for i in range(low, high + 1) if nums[i] == rightMode])
            return leftMode if leftModeCount > rightModeCount else rightMode

        return majorityElementRange(0, len(nums) - 1)

    def majorityElement2(self, nums: List[int]) -> int:
        """
        hashmap法
        :param nums:
        :return:
        """
        numsLen = len(nums)
        import collections
        mp = collections.defaultdict(int)
        for n in nums:
            mp[n] += 1
            if mp[n] > numsLen // 2:
                return n
        # 等价于下面的写法
        # mp = {}
        # for n in nums:
        #     mp.setdefault(n, 0)
        #     mp[n] += 1
        #    if mp[n] > numsLen // 2:
        #        return n
        # print(mp)
        return -1

    def majorityElement1(self, nums: List[int]) -> int:
        """
        随机化:
        每次随机选择一个数然后统计出现的次数再进行判断
        :param nums:
        :return:
        """
        import random
        numsLen = len(nums)
        while True:
            r = nums[random.randint(0, numsLen - 1)]
            count = 0
            for num in nums:
                count += (1 if num == r else 0)
            if count > numsLen // 2:
                return r

    def majorityElement(self, nums: List[int]) -> int:
        return self.majorityElement1(nums)


if __name__ == "__main__":
    nums = [2, 2, 1, 1, 1, 2, 2]
    # nums = [3, 2, 3]
    print(Solution().majorityElement(nums))

# leetcode submit region end(Prohibit modification and deletion)